#!/usr/bin/python

import time
import math

t1=time.time()

limit = 10**6
print limit
pTable = [1,1]

penTable=[0]
for i in range(1, 250):
    p = i*(3*i-1)/2
    penTable.append(p)

#print penTable.pop()

for i in range(2, 59999):
    ss = 0
    for k in range(1, len(penTable)):
	# or break
        if penTable[k]<=i:
	   ss = ss + pTable[i-penTable[k]]*(-1)**((k+1)%2)
        if penTable[k]+k <= i:
	   ss = ss + pTable[i-penTable[k]-k]*(-1)**((k+1)%2)
	if penTable[k]>i or penTable[k]+k > i:break

    ss %=limit
    if ss == 0:
       print i 
       break
    pTable.append(ss)

#print pTable.index(0)

print time.time()-t1


